package com.dyz.baseAlgorithm.searchAlgorithm;

/**
 * @author: daiyizheng
 * @date: 2021/5/14 12:50
 * @description:
 */
public class InsertSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
        int index = insertValueSearch(arr, 0, arr.length - 1, 1);
        System.out.println("index = " + index);
    }
    private static int insertValueSearch(int[] arr, int left, int right, int findVal) {
        System.out.println("插入查找次数~~");
        //注意：findVal<arr[left]和findVal>arr[right]必须需要，否则我们得到的 mid 可能越界
        // findVal < arr[left] ：说明待查找的值比数组中最小的元素都小
        // findVal > arr[right] ：说明待查找的值比数组中最大的元素都大
        if(left>right || findVal < arr[left] || findVal > arr[right]){
            return -1;
        }
        //求出mid，自适应，额，这不就是一次函数吗
        //findVal = arr[left]时，mid = left
        //findVal = arr[right]时，mid = right
        int mid = left + (right-left)*(findVal - arr[left])/(arr[right]-arr[left]);
        int midVal = arr[mid];
        if (findVal > midVal) { // 说明应该向右边递归
            return insertValueSearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) { // 说明向左递归查找
            return insertValueSearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }
}
